package com.cskaoyan.com.ex;

public class Ex2 {
    public static void main(String[] args) {

//        判断链表中是否有环(circle)
//        反转单链表
        Node e = new Node("e", null);
        Node d = new Node("d", e);
        Node c = new Node("c", d);
        Node b = new Node("b", c);
        Node a = new Node("a", b);
        // a --> b --> c  --> d --> e

        e.next = c;
        // a --> b --> c  --> d --> e --> c --> d --> e --> ....

        // 判断链表中是否环
//        boolean bool = hasCircle(a);
//        System.out.println(bool);



        String value = getHeadValue(a);
        System.out.println(value);
    }

    /**
     * 在已知前提:  一个具有环装结构的单链表
     * 获得这个环装结构的头的位置结点存储的内容
     * @param head: 原单链表的头结点
     * @return:  单链表中环装结构头位置结点存储的内容
     */
    private static String getHeadValue(Node head) {
        // 快慢指针实现
        Node f = head;// 快指针
        Node l = head;// 满指针

        // f.next != null && f.next.next != null
        // 表示快指针的下一个结点存在, 下下一个结点也存在 --> 向后走
        while (f.next != null && f.next.next != null){
            l = l.next;
            f = f.next.next;
            if (l == f){
               // 获得相遇位置
                break;
            }
        }
        // f 和 l 在环环内相遇:  f和l就在指向这个相遇位置

        f = head;
        while (f != l){
            f = f.next;
            l = l.next;
        }
        // f和l 相遇位置, 就是环的头的位置
        return l.value;
    }

    /**
     * 给定一个链表判断链表是否有环
     * @param head : 给定链表的头结点
     * @return : 是否有环
     */
    private static boolean hasCircle(Node head) {

        // 快慢指针实现
        Node f = head;// 快指针
        Node l = head;// 满指针

        // f.next != null && f.next.next != null
        // 表示快指针的下一个结点存在, 下下一个结点也存在 --> 向后走
        while (f.next != null && f.next.next != null){
            l = l.next;
            f = f.next.next;
            if (l == f){
                // 说明, 快指针在向后走的过程中通过环绕回来了, 进而和慢指针相遇了
                return true;
            }
        }

        return false;
    }
}
